package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/16 16:33

 约瑟夫环问题：
 暴力法：vis[]记录是否访问，计数为1时停止
 数学：
 设当前状态n人，报数m出列；表示f(n,m)为留下最后一人的编号
 假设报到m-1出列后，m-1之后编号：
 原：m,m+1,(m+2)%n..
 现：0,1,2
 则有：原=(现+m)%n
 即——f(n,m)= (f(n-1,m)+m) %n;
 */

public class Main31 {

    public int func(int n,int m){
        if(n==1)return 0;
        return (func(n-1,m)+m)%n;
    }

    public int LastRemaining_Solution2(int n, int m){
        if(m==0)return -1;
        return func(n,m);
    }


    public int LastRemaining_Solution(int n, int m) {
        if(m==0)return -1;
        boolean vis[]=new boolean[n];
        int cnt=0,t=0;
            //用取模，模拟循环
            for (int i=0;cnt<n-1;i=(++i)%n){
                if(vis[i])continue;
                t++;
                //此时报数为m-1
                if(t==m){
                    cnt++;
                    vis[i]=true;
                    t=0;
                }
            }
        for(int i=0;i<n;++i){
            if(!vis[i])return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Main31().LastRemaining_Solution2(2,3));
    }
}
